package LeetCode._01_树;

import java.util.LinkedList;

public class _297_二叉树的序列化与反序列化 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
    }

    // 后序遍历序列化二叉树
    public String serialize(TreeNode root) {
        if(root == null){
            return "#";
        }

        String left = serialize(root.left);
        String right = serialize(root.right);
        String subTree = left +","+right+","+root.val;
        return subTree;
    }

    // 将序列化后的字符串放进一个链表中
    public TreeNode deserialize(String data) {
       if(data == null || data.length() == 0) return null;
       LinkedList<String> nodes = new LinkedList<>();
       for(String s:data.split(",")){
           nodes.addFirst(s);
       }
       return deserialize(nodes);
    }

    //接收一个链表，对于后序遍历，第一个是根节点
    public TreeNode deserialize(LinkedList<String> nodes){
       if(nodes.isEmpty()) return null;
       String str = nodes.removeFirst();
       if(str.equals("#")) return null;
       TreeNode root = new TreeNode(Integer.parseInt(str));
       root.right = deserialize(nodes);
       root.left = deserialize(nodes);
       return root;
    }

}
